package com.wang.sort2;

/**
 * @Author: along
 * @Create: 2021/4/19 12:11
 * @Description:平衡二叉树
 */
public class Demo16_IsBalancedTree {
    public static class Node {
        public int val;
        public Node right;
        public Node left;

        public Node(int v) {
            this.val = v;
        }
    }

    public static class Info {
        public int height;
        public boolean isBalanced;

        public Info(int height, boolean isBanlanced) {
            this.isBalanced = isBanlanced;
            this.height = height;
        }
    }

    public static Info process(Node node) {
        if (node == null) {//base case
            return new Info(0, true);
        }
        //递归左树，右树
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        //拿到需要的信息
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        boolean isBalanced = true;
        if (!leftInfo.isBalanced || !rightInfo.isBalanced || Math.abs(leftInfo.height - rightInfo.height) > 1) {
            isBalanced = false;
        }
        return new Info(height, isBalanced);
    }

}
